N=5000;
m1=26411;
m2=1;
S=[4507613,11,61676257,1,1,49,1,7,4714787,1,278773,72247,11,77,501851,70001,1,253939,642444847,23719,1,1,1,1,1,1,11,13751,1201406189,11,1,1,499367,7,1,1,1,7,85601,1,1,222929,1,25673,11,1531,413833,357847927,11,11,7,1,2964577,1,42719,1,1,9949,1,1,1,1,1,1,1,165067,1,1,1,223817,1,1,1,1,11,1,11,8681,7,420871,28607,11,77,7,1,37057,161189,1,179892149,90901,706462031,70067,996193,448091,266581,1,1,7,1,1,1,77,1,11,1,9091,11,53171,1,1,1,1,50437987,806824969,1,18521,111463,65729,539,7,1474016243,88813,218869,11,1,1,1,7,1,88891,1,70879,612182503,11,11,1,1,1,86311,1546262603,77,1,252749,36781,1,178517879,11,86291,1,11,7,49,74767,7,1,60689,1,1,11,1,1460142907,1,1,26861,1,1,77,79987,2921723,1,86297,1587381181,1,36677,21859,236687,77,1,7,368081,1,56687,331373,1,121,79813,85531,7,342419,1,1472640161,7,7,12893,1,1,65777,1,11,665623,77,11,7,11,1,1,1,11,7,1565956381,71971,31231,1,77,23059,1,1,1,7,652733443,908743,7,1,279499,46639,1,44867,604009,77,49,1,1,1,1,1,1,718399,46519,1,409759,7,87991,1860534697,7,1,1,7,7,63857,453019,1,7,11,1,1,533827,905787917,1,3086699,1,31741,1,11,77,1,1,11,7,301499,58679,1,7,7608139,585459887,1,121,1,1,11,11,1,121,1,91063,1,1,1,1,318521,11,7688461,212554657,61001,26783,1,38917,481349,46459,229465393,79693,1,2311,1,552679553,32831,72623,1,1,77,11,77,7,1,1,7,1,164717,1,121,1,498197,413369,319669,629839,11,11,827987089,1,1,1,7,1,30241,164899,342529,5198281,17203,686077,1,1,26099,16267,948673,121,87517,1,1,458909,1,11,7,7,64633,1,11,24623,61033,1,7,41229419,49597,964411,1,1,7,79549,2635367,734393,121,332731,11,7,1,94541,1,1,1,1,1,1,539,60521,1,667891,1,1,1,1,136323319,7127,1,11,1,7,11,185507,1,77,1,7,1,77,1,1,84029,1,1,1,1,11,504450539,11,15499,55799,801779,3691,121,8963,27763,7,11,11,1,9029,49,11,11,503531,77,7,911977,1,5323,11,670087,1,87011,11,7,7,40433,77,965767,260579,68749,1,1,7,1,84737,1,1,11,243984113,1,1,1,572873,1,11,20983,1,19687,21011,237611,14971,66169,20693,26701,1,1,36871,953174293,71287,154259,26981,7,1,1,1,1331,121,805013,26883703,847,1,11055649,32119,1,1,107,9007,54983,1,219709,11,1,432751,1,1,7,2369297,1,519071461,7,36923,938333,11,1,1,1,1,1,726381307,7,7,7,484979,236299,1,46981,7,381161,121,1,584419,58757,1,7,58831,7,7,96221,1,1,11,5995187,1,93479,7,1961869579,49681,1,61057,77,1,105091,4182563,1,1,7,148027,1,92993,1,11,1,9521,1,438493,49,1,1,5857247,71647,46133,1,473170823,199241,642521,1,514987,94661,658693,63283,7,1134420383,1,500171,68279,953,361163,34673,33641993,1,30119,1017577,1,1,9758771,45343,1,1,11,16691,469667,7,39443,77,99181,1,1,1488314207,1,334159,1,7,49,1,10639,26921,11,1,4186567,3413,652603,1,7,3735319,74687,83471,1,25579,49,308497,7,1,11,7,34097,117509,4881503,1,66509,7,29023,523831,95083,2165471,543347,1,570829,159523051,2888039,1,18199,35731,1,21139,11,77,1,49,1,1,7,3175711,1403053069,680273,1,4840297,11,28307,1849508417,121,11,1,1,7,853514821,1,6637,49,1,1,1,11,995071309,77839,84961,1,72973,1536700453,175777,1,24101,1230318179,80831,77,7,77,398519,343,60083,1,1,297101,8468911,11,39857,1,11,1,7,465839,50069,4418953,1,91957,1,49,1,1,31601,28477,1,1,847033,3773,77,1,77,77,121,51257,7,7,77006251,247037,49,6043,121,11,49787,116479,847,1,7,5577187,849902939,49537,1,35839,11,11,1,28729,81899,66527237,1,68597,7,1,7,77,1,1,1,1,2593,7,263534639,1,10427,246389261,1252559,21757,1,967161631,8537,1070951371,1,1,81173,7,75967,1,135091,19609,1664509,311,1,1,11,1142524519,24391,7,68023,1,76003,1,7,1,7,422359,829,2738561,1410256177,1,1,697829,49993,509003,1,4347959,1085655179,11,1,11116633,14238959,96221,8741,1068749,1,58498831,230543279,1,11,1,1,71359,1,1,89371,45943223,1509517109,1,93979,1,1,257,956461,1,33343,1,121,1,1,25621,354193,42677,33967,1,7,77,970566997,1,1765138187,12379,3932467,11,11,7,1449692081,1,1188651151,83777,98873,633059,1,1,97512241,1,71089,11,27529,1,584297,143017,1,43321,263543,11,7,7,1,77,4104793,384791,86767,11,539,503445727,1,173,11,1,121,164941,1,539,6737401,35083,11,11,11,1,1,1,1786981,1,1,191741,11,49,222013,1,7,688877,7,1,121,93329,77,64591,1,77,1,1,1,35831,1,11,1,22349,60851,7,1,1,11,154561,69001,1,463,1962126703,1,1,3773,1,57179,1,7,95651,1,11,142021,1,1,2087,11,1,1,1,1,11,16369,7,1,570941,77,69811,1,2822639,777227,11,11,654247,1,708228457,1756156747,1,1,4073,690487,84067,11,1,1992018209,1,7,7,1,1614019,1,49667,99989,1,1,26981,121,11,1,77,1504428899,11,1,11,455623,456577,1,71239,7,967,1,1,48473,9067,11,1,63527,1,11,1,89627,41279,1,1,292439,45191,28087,1,1,310211,99257,27517,11,50873,1,7,1,1,394400707,7,1,1,7,44249,1,1,7,48761,16363,1,1,77,72859,1,7,1,11,1,7,1,29437,7,1,49,1,82811,533797,1,8963,30047,1,1,539,514217,614369,1,77,1,7,1,1236927431,2225993,7,11,121,2111,1,1,706070083,96451,77521,1,1,37013,1,2099,7,121,660247,733983307,27961,11,25603,1,77,9901,11,13931,13816007,7,32189,1,1,1,1,31391,1,1,92009,11,11,14437,77,1,98717,1,50743,1,7,1,41389,1,11,996709,7,1596803311,74201,36061,409,31727,1,1,11,51329,77,41539,49927,91733,22843727,121,81761,1,79040447,20929,11,1,1,1,1,1977649307,1,1,1,1,65443,1,7,25463,712393,1,7,1,857,7,11,7,1,1,7,5843,7,1,98873,14423101,65519,1,131201,770617717,11,339823,7,63493,358831,554215787,1,26687,1,41299,1,1,1,1,1,1,9187,1,1,7,17401,13781,11,11,10180577,1,7,1,1663,530431,1,902737,36791,221543,289698739,959,7,1,1,1,71503,1,13597,11,1,4801159,7,57413,1,1080827,49,1,1,49,2389,1,11,77,1,313423,381159349,1,1,77,1,648151,797,1,1,89597,1,539,77,1,746417,410599,77,1014959,62011,92479,11,81173,77,87977,1,43649,11,36032689,1,550759,1,3049,1,7,1609111,121,1,97493,1,11,1,11,1,763741,76541,1,1,1,121,563747969,11,9817,1,27689,11,1,1,1,264253,11,1,349,1,7,77,98467,11,11,86837,1,1,11,1,97493,1,1,1,1,1,76837,17971,1,47789,33577,41519,1,1,93251,1,11,4627,73939,9749,11,1099381601,7,1,69493,1,290801,94379,1,1,1,1,53699,49,11,7,343849,1,1,1,257719,237479,343399,1,2343131,1,74567,64891,11900471,1,7,80911,11,1,91493,1,37847,41597,3482941,1,1,7,97159,721787,11,74219,1,1,178171,1,6581,1,7,1,7,847,7,1,1,11,7,8623,4621,1,1,1,11,44077,6157811,7,53896183,1340732519,22067,11,1,1,1,894091,8623,7,11,1553,52747,57859,77,3517,7,7,33071,42701,1,21559,11,5869,1,1,20430487,1,1,92791,1,1,74353,1,512149,58271,1,1,85453,121,1178086219,1,64489,1,36107,1,7,445768897,7,11,121,206115461,1,1,1,1,7,1550173363,7,1,1,1530827117,1,11,551873,36467,5983571,97931,1,1,11,7,121,1,414379,5909981,7,1,8287,1,1,1,1,7,1,775511,29113,1,457708877,7,62927,1,11,1,33589,29269,32611,1,11,1,45181,1055879,1,1,806099,1,1,7,1,1,1,49,7,121,1,17183,7,7,1,40253,38861,1,539,78607,1667752199,49,11,1,1,1,1,41190919,34261,77,1,1,4036277,11,1,28493,124372087,7,65579,248281,1,1,11,7,26820241,4045489,26851,22267,53927,8527,1,11,58961,7,75109,121,11,10729,343,1,7,72559,1,1,1,421333,641033231,1,11,1,10259,4111,11,11,1,1,1,95401,1,706541,484649,1,994343887,1,436177,11,11,330517,1,1,7,46771,11,1,1,593159,7,77,25579,11,52103,11,40927,7,7,1,344971699,550039,1,1,1,68791,1,1,1,1,7,7,1,11,11,369070519,121,11,121,253337,1,11,1,387937,11,7509271,11,7,11,1,176281,1,11,52783,1,1,121,1,11,1,56311,1,1,1,77,1,4049,1,1,639389,7232291,11,11,1,11,1,121,1,1,1,1,1,1,7,11,1,11,22259,1,80149,607387,2441,222739,1,1,1,1,1,11,1,121,51551,34231,995203,87211,18773,1,247807,34631,260381,1,95063,11,66851,7,1,11,466756153,247373,799711,1,1,232561,84857,1205922169,63773,11,77,66919,1,1,1,1,7,77,49,7,1493,7,1,670481,1042428223,1582905707,7,11,66383,1,1,28747859,1,759011,35081,2087393,73849,78569,814482001,1,1,7,32653,78737,7,1,11,243727,24043,159973,1,9203,7,61291,45191,11,1,1,1,71209,1,1,1,1,1,1,48481,1,83461,1,1,70459,253121,548429,1,49,7,11,4386151,1,1,1,11,1,1,11,84047,1,1,1,11,93557,11,1,21391,1,1,1,1,659911,1,1,29201,7,79873,7,7,494483,11,4172927,11,7,97007,1,204337,1,1,91129,1,649019,11,1,95923,480067,291467,1,11,77,487,90353,98729,763120859,77,7,1,121,1,1,7,1,1,7,527023,1,1,1,1,7,457846817,7,1,450598087,6373,33199,51713,1,337733,7,21397,1,1,1,51869,11,1,1,64763,2753,27803,1,7,7,77,59919319,11,1,11,1,11,568379,77,377509,791566109,1,1,1,2464649,11,91591,843074533,622501,11,10211,139391,1,1,26981,1,1,11,1,1,7,1714997699,121,1,7,1097723,49,349,11,1,1,1,1,170423,567497,11,52640147,11,49,1,1,50231,19717,72317,1,11,6607,1,1,32341,225422767,1,1,49,582803927,1,377707,1,77,2705143,80749,1,11,29491,14713,1,7,96451,53767,11,1,51193,1,11,59663,1,1,94531,1693,7,11,1053134639,982981507,13477,1341722047,1,1,77,28649,1,1028753,41232151,32839,1,1,1,1,1,1,7,1,1,7,785257,11173,7,1,71387,121,1,77,25040323,7,1,49,93083,1,1,284137,1,346841,23339,51871,7,112733467,7,1,1,11,92107,1,11,1,7,7,1,7,7,11,31477,1086618097,1,670019,72383,1511,1,1,1,11,1,1,1,399287,47500607,1,11,1,17350949,176183,11,1,10601,11,28607,1,77,77,1,1,1,58439,1,1,1,1,1,399749,64901,952897,684778099,16181,1,1,1,12569,7,41521,36451,1969678541,1,348422881,223029431,66121,1,398923,1,1,11,1,569,121,7,603127,571403,7,11,7,11,847,77,668107,77,1,11,7,49,1876063,10357,255857,1,409,7,1659628291,11,686077,24989,1,7,7,96017,1,1,1,15083,1,1,1,1,427903,1,1,1,11,7,1,1,11,1,65581,1,11,1,95317,121,58687,7,7,1,121,1,1,1,7,7,1,1,1,7,99449,7,4134691,11,847,11,54979,1,7,19733,7,11987,5009,860651,3691,1,11,63100529,11,7,7,251977,1787047177,1,7,26947,1,136631,34537,4951177,16091,67651,11,1,146503,174091003,11,1047884933,77,7,1,1,488508097,62039,11,31321,1,1,7,1,1,64743967,60943,48163,232337,53129,1,39163,7,811481,1,6787,1,27367,7,1,247219,70009,1,1095281,1,6882799,121,536899,1,1,91763,2239,798743,359777,593,1,7,24821,441217,1073083,7,10597,287917,547,49,11,27481,672345149,1,54401,66583,10831,1,790339,7,44651,1,11,370007,148099,11,18667,84229,121,66431,1,12841,425161,1,1,1,121,663467,94837,83563,20063,7,1,1,51829,7,349447,1,1,1,1,56333,7,7,10321,1,1,27041,1,11,2027,864853,1,7,11,9414713,7,7309,1,7,1,1,77,1,1,5805107,1410908857,1,1,11,20743,1,49,1,277079,3491,11,7,1,7,11,184247,7,38567,1,1,1,1,1,7,1,1,1,1,317149,1,6337639,11,1,36931,7,1,96353,36011,1,25711,11,1,64799,177551,330209,11,1,1,416339,49,208549,11,1,11,2179793,10771057,32779,16177,11,1,1,1,1,11,7,1,300601,926568233,1,1,121807,219307,74923,38027,1,59707,93139,1,1,52757,7,1,1,508529,1,66347,499,7,1,6689,16651,1,15259,99391,11,1,11,91583,4027177,78517,1,77,11,7,10584959,37748701,1,45463,1,58246961,323719,11,1,207487,1,193567,11,67213,1,11,305344691,36923,121,354013,1,1,1,1,1,17789,7411,1,1,1,7,67421,1,13903,775577,1,11,77,34127,7,1,1,1,23603,151161529,7,1,17327,364177,1,7,49,308119,1,7,7,13963,7,1,76367,77,1,98143,11,11,7,65647,35993,11,195019,11,1,77,5699617,1,1,539,5209,1,214879,1,1,102431,71821,67447,1,1,307153,778613,1,1,1,1,411187,13264867,38317,11,1,7,245161,6899,7,47041,1,7,33767,1,1,864347,74759,1,7,58789,11,92957,7,33721,1,11,1,2123,39799,1,624421,7,13751,868821281,126137,1,11,74131,670153,616232689,1,11,1,49,373807,1,11,1,1,790757,11,83267,49,1285382131,1,1664641,1,1,55139,1,77,1,88211,1,1,11,1,7,11,1,1,104237,1,1,6073,11,1,7,1,57251,1,7,1,26783,1,408541,7,1,11,55399,928301,1,255157,23209,7,1,32309,1,1,278839,1,7,7,28069,71363,172982393,1,1,7,1,121033,21,43609,1,1,11,1,32974637,1,1,61357,1,1,121,1,1,1,71473,9433,11,1,1,1,7,77,1,412853,1,1,1,24317,205709,162169,817553,11,23447,1,7,71597,352847,1,26687,1,670307,1,9317,1,1,21587,43075879,1,1,77,11,1,121,77,72253,1,976987,237787,7,77,7,49,11,1,7853,1,1,82049,39983,1948274567,12049,1387100753,1,1,7,11,1,1,641,477197,7,93083,92311,81157,1,12301,71909,1,36343,1,14947,1,7,7,32323,1,30089,1,292691,23399,15493,1,1,209359349,117953,80233,1,1,1,1,7,11,11,1,1,7,1,7,1,1,16033,77,1,1,1,1,85091,538943849,1,1,29977871,66529,49,1,87187,7,151039,1,315139,1,48611,1,344251673,29863,564683,59884933,11,1,1,104881,193567,121,7,1,11,1,11,74723,1,6883,1,1,77,1,1,11,77,1,221903,248227,69461,1,33391,1,7,1,7,11,7,1,1,4556363,1,11,92479,1,7,1,1,11,4401229,7829,31849,498743,7,7,1721096093,1,1201,1593691,1,850487,1331,1,1,1,32401,7,969541759,1,932107,47809,1,1,82213709,1,47939,11131,1090133,7,1,1,1,7,15541,641417,7,5651,7,7,1,1,1,1,7,29867,11,7,1,5557,1,7,490693,305833,1,72167,1,1,272393,81671,1,1,317149,11,401,11,1,5456759,11,55,349,43481,72223,1,1,1,1,1,352688983,263647511,1,307279,1,371459,77,77,9001,1,1,1,11,1,25339,1,1,49,1,79159,54583,1,985171,6212503,1,59023,11,1,1,1,7,823427,72229,48787,8999,1,277717,361151,942337,7,1,11,1,73043,1,1,1,1,1,63541,224851,7,1,7,1,816254539,1,1,59999,121,1,1,11,1,8599,7,13139,11,49003,1,121,7507,1,7,121,77,11,290625473,1,1,49,1,7,7,46471,79259,1,53777,1,1,49,1,9829,1,1,838541,1,1,1,7,49,1,99013,1,1,1,1,11,1,62219,1,590723,626927,32323,1,49,801713,1,1,778651241,121,282023,113311,11,11,33703,1,1,11,76326223,1,11,1,343,77,7,5953,1,17,7,266483,9739,1,11,1,7,1,228221,1053811,81637,62209,87853,10094183,18691,49,65651,7,7,321673,663551,215719,671473,7,10273,1,1,7,51797,37897,49,1,478519663,11,1,11,1,1,47207,1,14779,1,33619,66169,1,1,202069,1,1,285791,38833,97651,1,1,896398027,11,1,1,7,16661,5879269,77,7,1,16843,77,1008319889,1,894553,1,1,1,33199,1,11,1,11,49,131,1,85487,77,7,1,7,1,1733,67453,67219,1,540953,1,7,397999,32099,44647,1,594391,7,1,1161652411,1,1,7,1,1,87421,75289,1,1,8147,1,13721,204253,49,19727,11,1,7,162421,49,33967,1,82351,1,7,121,1,1,726451,1,1,7,430451,1,1,503393,7,3449,411670379,1,150451,73025561,1,7,1128110593,24413,86131,49,1,97369,1,1,11,77101,1,14561,3604469,1,391307,1,7,1,1,1,1,121,1,1,1,1,11,2591561,1,1,39709,4289,77,688261,73069843,1,15907,1,7,1,1,63311,1,91369,1,1952349809,53003,1,1,99559,84584207,80531,1,1,75979,1,30011,1,11,34657,17389,1,1,11,1,1,1,1,7687603,81559,7,1,1,236687,1,1,24499,77,1,515647,49,7,797,306019,2196029,1,1,1,1,1,1,77,8779,51913,7,1,1,1,1,1,1,1,1,505367521,1,356373781,7,332017,11,7,11423,1,1,1,1,121,1,77359,1,7,1,80347,11,1056869,1,70009,49,14563,1,7,267911,1,1,46727,48859,67339,3947,7,7,7,907857479,1,134099,606193,1,1,137039,11,1,42901,1,1,488289383,22861,1,1,7,1,11,7,65581,1,77,11,1,1,7,1,1,7,555643,515537,76031,49499,7,1,7,77,1,46193,1,1399256753,1,4583,1,1986941,30661,1,1,864413,1,252307,1,11,1,1,135077173,1,1,479,1,11,47543,1,1,7,1,1,77,1,793529,1,190208089,7,7,1,1,1,1,633281,2655191,7,1,1,1,77,75211,953579,77,205877,7,78101,77,1,15559,11,11,11,1,77,7,1331,1,35447,32347,1,1,11,1,54101,1,1,1,571,539,77,21031,1,1,1011414367,77621,1,1,49,1,77,1,11,1,1,1,52541,11,171061,90067,7,39397999,1,1,1,23269,315271,1,1,1,1394278721,886589,1,1,1,539,15917209,1,72547,11,540743,1,1,1203829,418517,1,362220679,1,1,68597,42463,596603,17209,80191,939961,11,11,366685729,64453,71129,610561,7,1,7,1,1274833,983389,1,41461,239129,77,11,1,1,1,1,92639,1,260513,7,425349091,49033,1,567539,1,1,39671,43543,7,1,1,11,1,847,1,73709,1,1,1,1,6076741,40841,40423,1,57781,410977,1,1,1,11,94903,94157,11,2417,9619,1,1,11,11,1,1,29423,9154013,36229,1,1,12433,7,11,7,7,11,1,85571,56111,22741,88121,1,1,1,1,7,11,9623,42727,632819,49,218537,1819027,1,11,65677,47917,11,705199,1,50111,36293,7,1,39607,1,63931,1,11,1007941,1,68669,80513,219779,11,11,1,7,77,22013,202830493,7,1,1,1,1213,1,1,90407,1,77,149737,1,1,1,11,425381,69959,72497,1,26903,554213,7,1,11,11,1,73,1,11,1,1,73351,1,1,1,48337,1,617639,1,25951,641347,11,106771,842840587,674757491,121,1,15227,45497,66361,11,77,11,1432772317,1,1,1,1,1,724537,77,1,65111,1,1,1,1,1,121,83579,1,817069,7,935678309,11,86137,1,7,41213,1,7,1,7,1,1,31687,49,7,1,10739,30391,1,71551,1,95143,1,13217,1,11,1,560879,11,1,35951,65003,76363,7,1,393481,7,1,1,1,1,1,263851,64817,1,121,1,61471,48300853,105952391,9697,1,1,1,11,84521,872839,1,11,5953409,813989,7,11,384277363,2650459,72227,54443,586994059,1,7,1,11,508753,86291,77,1,1,1,1487563,121,7,1,1,1,1,1,1,1,1,7,7,1,69899,66067,1,135023,11,11,11,11,1,33851,49,11,1485703133,1999,121,1,52361,48857,6875561,58043,15901,627823,1,1037201,1,1,1,305028379,1,326543,11,42829,86573,1,7,1,11,86209,1,636889,415583,1,7,841577,1,1,396403,1,60533,1,1,7,32603,1,983,31723,1,77,84659,568379,79973,437926789,12511,863621,45869,1,7,7,46451,1,386603,11,1,1,1,176671,84913,1,1,499829,27791,52567,11,121,131084921,7,517187,14143,1,11,1,1049719,1,1,1,1,73693,84481,7,61363,1,1,77,4111,77,11,7,139490341,1,64921,877732421,49,1,1,34471,19961,541277,127429069,1,1,1,11,1,20357,680617,7,1,1,7,54833,1,572971,433081,1,7,1,603743,1,1,1,5009,41189,1,32633,1,127972463,7,11,1,6376337,1,74201,1,73271,11,7,15313,1,11,1,1,14627,984247,219923,1,7,12263,193312507,1,1,25785463,1,1,11,63617,60889,7,1,11,11,1,11197,7,1,1,539,46573,847,1,75128351,1,27487,15955241,7,38501,9811,538417,160061,7,11,11,1,1,13,11,1,7,29027,11,11,1,11,81101,11,17923,1,1,1,414887,49903,1,11,1,1,7,11,7,902145329,7,7,77,11,7,307351,1,1,77759,1,7,1,1,1381,10223,7,1,28477,89231,423071,1,553973,5929,11,1,29941817,7,94621,11,1,11,24683,1,1,1,19469,1,11,30773,6299,94747,7,1,1,83357,228613157,36131,10364981,11,1,1,1,146212463,16453,11,7,11,1,7,1,57899,79397,11,1027848551,1,156739,54373,1,49,1,54547,11,78379,11,71293,1,1,7,1,11,36887,1,1,7,1,1196272261,11,1,7,71731,257747,1,96989,1,90407,692659,77,7559,20249,9697,377113,11,753414521,7,11,30881,1,294539,1,3886399,1,1,118097,11,7,1,33457,524111,64451,1,567287,7,36107,11,1,1,1,7,67261,1,77,7,66293,11,35153,87877,91159,94253,126181,7,11,26681,1,1,19801,1,11,97859,1,1,42816697,12743,539,4951,11,24023,1,7,63533,65927,539,7,1,29423,7,1,49,7,4744201,1,1,77977,1,578137,1,1,1,1254292331,11,1,11,1,1,77,69127,7,1,73421,286540669,1,7,18143,62477,645547,1,11,25739,1,539,1,151636837,1,77,9127,10831,1,1,1,12907,1,49891,11,1,1,1,1,11,41659,1,7,1,1,33547,21871,1,11,77,7,343,35569,97373,1,1,11,11,25673,11,1,343,553441,11,177247,70289,1,121,1,17539,98347,328691,11,77,17681,1,77869,1,1,7,339691,1,43477,73883,1,91033,11,1,77,19789,1,184877951,1,1,1,7,11,1,149083,7044499,587909,1,1,7,2248757,300923,54983,77,1,45613,70973,1,1,486250067,7,53093,7,1,1,1,145178233,77,1,5661733,47969,1,1,1,1,984643,11,11,2965921,11,1,1,7,39241,1,259391,1,1,1,1,7,70227311,74377,244554433,110067041,659791,1,13223,1,11,381493,1,1,539,1,971,153989,745547,7,81611,1,7,200641,1,1,59009,81371,95857,238399,1,41489,1,166327,11,1,11,1,460103,1,665467,11,7,7,1,28387,1,1,7,4342261,121,1,11,4613,7,1,96769,91583,7,1,11,167849,328020139,15749,526883,1,17389,9547,1,59663,7,11,7,1,1451142773,11,1,11,32971,78455069,22444891,1,1,7,32491,11,11,4845463,28349,421519,1,1,7,61603,64891,445357,11437,1,11,255941,1,1,1,1,26653,1,7,42443,1,1,1,11,992489653,1,11,1,7,9337,7,1,49,1,1,878053,11597,1,1,1,343409,1,55171,1,1,1,11,1,11,11,1,1,81671,598283,1,51109,11,54437,38669,62989,1,1861013,41081,77,1,1,7,88337,7,1,7,1,6619,1,290549,1,1,27581,1,1,11633,11833,11,147921421,40771,7,533029,7,44041,46451,11,11,1,1,1,22123,1,49,61211,1,135821,1,1,1789,11,60700033,7,1,1,1,24061,15193,49523,79229,670087,7,753000223,1,56813,1,779251,1,11,1,38729,56099,7,1,7,49363,726979,48989,56963,689101,1,10689019,1,724407187,618247,530071379,7,460823,1,1,10259,1,1,51439,11,9851,20509,188489,11,634879,58771,35171,37699,1,14407,31757,42902123,1,20089,39841,11,1,1,1,1,537559,1,1,11,1,7,1218152413,1,7,7,49,470309,1,7,90547,28879,72469,1,57107,1,7,560219,3945137,680197,1,1,1,11,7,1,1126433,1,1,151349,11,11,7,74587,56747,7,539,1,1,1,285313,39103,11,11,1,1,8076629,1,1,475153,245987,436909,539,2891119,1,1,1,7369,209759,1,5219291,1,57373,1,13367,1,1,719,1,67181,11,123343,7,623298947,1,262619,11,8129119,71551,1,1,1,68633,1,554911,239519,1,79231,1,7,1,1,11,7,489841,74077,7,1433527171,121,1,1,1,1,11,1,11,77,1,7,1,1,3482941,7,1,1,1,1,1,1,1,343,11,77,97259,513919,7,15383,13831,1,52103,128149,735251,52609,30701,7,59863,1,49,11,1,211536821,17093,7,1,67763,49,11,1002683,31973,63541,15671,11,931513,1,7,1,1,1,1,94463,1,56101,1127953127,1,1,77,1,11,1,95219,1,74301653,1,99817,11,7,1,1,191,17623,1,1,1,556843,52249,16073,97073,1,1,716496557,77,24953,8461,1,1,84589,11,1,7,1,25541,64621,1,1,11,1,432773,1,1,253461907,11,7,11,1,1,35731,1,1,49,338899,654409,64007,7,7,1,11,7,41543,1,64013,1,7,1,1,412979,7,1,311069,1,1,539891,1,49,7,1,49,1,7,1,31189,366179,1,1,1,1,1,6379,6733,7,77,677579,363251,1,81063829,7,1,1,7,1,23669,7,1,78301,97967,11731,7,1,7,1,7,77,7,1,36979,1,7,1,1,7,9059,11,3061,1,432691,1,7,451759,7,7,7,1,104003009,1,31259,39937,1,11,1,42361,1,7,1,88169,847,1,7,1,11,85021,29303,1,1,1077637,1,11,77,1863528473,1,11,1,35353,1,252365029,11,1,1,48131,1005389839,333817,668135837,1,11,1031,1,7467383,7,80423,49307,87959,715561,1,7,1,29611,1,11,1,1,1,126833,96739,1,77,1,1,11,191936113,1,7,7,1,25951,11,7,406140721,1,7,4289,1,1,21323,2158891,1,12113,1,1,1,18461,1,7,49,7,1,7,1,1,1,1,7,77,1093,7,98297,1,11,11,191873,75397,7,1,1,765297493,71633,3347];